package lpg;

import java.util.ArrayList;
import java.util.List;

class LookupTable<K, V>
{
    LookupTable(int initialCapacity, float loadFactor)
    {
        if (initialCapacity < 0)
        {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY)
        {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
        {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
        {
            capacity <<= 1;
        }

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = newEntryArray(capacity);
        pool = new ArrayList<Entry<K, V>>(capacity);
    }

    LookupTable(int initialCapacity)
    {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    LookupTable()
    {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = newEntryArray(DEFAULT_INITIAL_CAPACITY);
        pool = new ArrayList<Entry<K, V>>(DEFAULT_INITIAL_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    private Entry<K, V>[] newEntryArray(int capacity)
    {
        return new Entry[capacity];
    }

    private static int hash(int h)
    {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    private static int indexFor(int h, int length)
    {
        return h & (length - 1);
    }

    int size()
    {
        return size;
    }

    boolean isEmpty()
    {
        return size == 0;
    }

    V find(Object key)
    {
        if (key == null)
        {
            return findForNullKey();
        }
        int hash = hash(key.hashCode());
        for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)
        {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            {
                return e.value;
            }
        }
        return null;
    }

    private V findForNullKey()
    {
        for (Entry<K,V> e = table[0]; e != null; e = e.next)
        {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

    K findKey(Object key)
    {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)
        {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            {
                return e.key;
            }
        }
        return null;
    }

    K findOrInsertKey(K key, V value)
    {
        if (key == null)
        {
            return findOrInsertKeyForNullKey(value);
        }
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K, V> e = table[i]; e != null; e = e.next)
        {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            {
                return e.key;
            }
        }
        addEntry(hash, key, value, i);
        return key;
    }

    private K findOrInsertKeyForNullKey(V value)
    {
        for (Entry<K,V> e = table[0]; e != null; e = e.next)
        {
            if (e.key == null)
                return null;
        }
        addEntry(0, null, value, 0);
        return null;
    }

    V findOrInsert(K key, V value)
    {
        if (key == null)
        {
            return findOrInsertForNullKey(value);
        }
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K, V> e = table[i]; e != null; e = e.next)
        {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            {
                return e.value;
            }
        }
        addEntry(hash, key, value, i);
        return value;
    }

    private V findOrInsertForNullKey(V value)
    {
        for (Entry<K,V> e = table[0]; e != null; e = e.next)
        {
            if (e.key == null)
                return e.value;
        }
        addEntry(0, null, value, 0);
        return value;
    }

    void insert(K key, V value)
    {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        addEntry(hash, key, value, indexFor(hash, table.length));
    }

    private void addEntry(int hash, K key, V value, int bucketIndex)
    {
        Entry<K, V> e = new Entry<K, V>(hash, key, value, table[bucketIndex]);
        table[bucketIndex] = e;
        pool.add(e);
        if (size++ >= threshold)
        {
            resize(table.length << 1);
        }
    }

    private void resize(int newCapacity)
    {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY)
        {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry<K, V>[] newTable = newEntryArray(newCapacity);
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    private void transfer(Entry<K, V>[] newTable)
    {
        int newCapacity = newTable.length;
        for (int i = 0; i < size; i++)
        {
            Entry<K, V> e = pool.get(i);
            int idx = indexFor(e.hash, newCapacity);
            e.next = newTable[idx];
            newTable[idx] = e;
        }
    }

    K key(int i)
    {
        return pool.get(i).key;
    }

    V element(int i)
    {
        return pool.get(i).value;
    }

    void push()
    {
        stack.add(size);
    }

    void pop()
    {
        int previousSize = stack.remove(stack.size() - 1);
        //
        // First, remove all the elements from the hash table;
        //
        int capacity = table.length;
        for (int i = size - 1; i >= previousSize; i--)
        {
            Entry<K, V> e = pool.get(i);
            int idx = indexFor(e.hash, capacity);
            assert table[idx] == e;
            table[idx] = e.next;
        }
        //
        // Then, remove the elements from the pool.
        //
        pool.subList(previousSize, size).clear();
        size = previousSize;
    }

    void reset()
    {
        Entry<K, V>[] tab = table;
        for (int i = 0, n = tab.length; i < n; i++)
        {
            tab[i] = null;
        }
        pool.clear();
        stack.clear();
        size = 0;
    }

    private static class Entry<K, V>
    {
        private Entry(int h, K k, V v, Entry<K, V> n)
        {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        private final K key;
        private V value;
        private Entry<K, V> next;
        private final int hash;
    }

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    private Entry<K, V>[] table;

    private final List<Entry<K, V>> pool;
    private final IntArrayList stack = new IntArrayList();

    /**
     * The number of key-value mappings contained in this table.
     */
    private int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     */
    private int threshold;

    /**
     * The load factor for the hash table.
     */
    private final float loadFactor;

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

}
